//
// Created by shenbin on 2022/5/10.
// https://leetcode.cn/problems/n-ary-tree-preorder-traversal/
//

#ifndef ALGORITHM_TRAINNING_C05_LC589_H
#define ALGORITHM_TRAINNING_C05_LC589_H

#include <vector>
#include <stack>

using namespace std;

class LeetCode589 {
public:
    vector<int> preorder(Node *root) {
        dfs(root);
        return seq;
    }

private:
    struct Node {
        int val;
        vector<Node *> children;

        Node() {}

        Node(int _val) {
            val = _val;
        }

        Node(int _val, vector<Node *> _children) {
            val = _val;
            children = _children;
        }
    };

    vector<int> seq;

    void dfs(Node *root) {
        if (root == nullptr) return;
        seq.push_back(root->val);
        for (Node *child: root->children) {
            dfs(child);
        }
    }

    /**
     * 非递归求解；
     * @param root
     */
    void dfs2(Node *root) {
        if (root == nullptr) return;
        stack<Node*> s;
        s.push(root);
        while (!s.empty()) {
            Node *node = s.top();
            s.pop();
            seq.push_back(node->val);
            for (int i = node->children.size() - 1; i >= 0; i--) {
                s.push(node->children[i]);
            }
        }
    }
};

#endif //ALGORITHM_TRAINNING_C05_LC589_H
